package com.geekbang.homework.WeekTwoHomework;

import java.util.*;

public class StopKFrequent {
    public static void main(String[] args) {
     int [] nums = {1,1,1,2,2,3}; int k = 2;
     int[] result =    topKFrequent(nums,k);
        for (int i : result) {
            System.out.print(i);
            System.out.print(",");
        }
    }

    public static int[] topKFrequent(int[] nums, int k) {
       //统计数组中各元素的出现频率
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
       //将Map转化成List用于后续排序
        List<Map.Entry<Integer, Integer>> entries = new ArrayList<Map.Entry<Integer, Integer>>(map.entrySet());
       //根据频率进行排序，需重写比较函数
        Collections.sort(entries, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue() - o1.getValue();
            }
        });
       //取出前K个元素
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = entries.get(i).getKey();
        }
        return res;
    }


}
